package problem.year2023.month05

import kotlin.math.max

/**
 * @author LiangMu
 * @version \$Id: Day01.java, v 0.1, 2023年05月01日 13:30 LiangMu Exp $$
 */
object Day01 {
    /**
     * 公司里有 n 名员工，每个员工的 ID 都是独一无二的，编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。
     *
     * 在 manager 数组中，每个员工都有一个直属负责人，其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人，manager[headID] = -1。题目保证从属关系可以用树结构显示。
     *
     * 公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。
     *
     * 第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属（也就是说在 informTime[i] 分钟后，他的所有直属下属都可以开始传播这一消息）。
     *
     * 返回通知所有员工这一紧急消息所需要的 分钟数 。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：n = 1, headID = 0, manager = [-1], informTime = [0]
     * 输出：0
     * 解释：公司总负责人是该公司的唯一一名员工。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/time-needed-to-inform-all-employees
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
        // 构建结构树
        val tree = HashMap<Int, ArrayList<Int>>()
        for (index in manager.indices) {
            val key = manager[index]
            tree.putIfAbsent(key, ArrayList())
            tree[key]?.add(index)
        }
        // 计算时间
        return dfs(headID, informTime, tree)
    }

    private fun dfs(cur: Int, informTime: IntArray, tree: HashMap<Int, ArrayList<Int>>): Int {
        var res = 0
        for (i in tree.getOrDefault(cur, ArrayList())) {
            res = max(res, dfs(i, informTime, tree))
        }
        return informTime[cur] + res
    }

    fun numOfMinutes2(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
        // 构建结构树
        val tree = HashMap<Int, ArrayList<Int>>()
        for (index in manager.indices) {
            val key = manager[index]
            tree.putIfAbsent(key, ArrayList())
            tree[key]?.add(index)
        }
        // 存放子节点的列表
        val children = tree[headID]
        var res = informTime[headID]
        while (!children.isNullOrEmpty()) {
            val tempList = ArrayList<Int>()
            var temp = 0
            children.forEach {
                temp = max(temp, informTime[it])
                tree[it]?.let { list -> tempList.addAll(list) }
            }
            res += temp
            children.clear()
            children.addAll(tempList)
        }
        return res
    }
}
